//package acm.蓝桥21;
//
//import java.io.BufferedReader;
//import java.io.BufferedWriter;
//import java.io.IOException;
//import java.io.InputStreamReader;
//import java.io.OutputStreamWriter;
//import java.io.PrintWriter;
//import java.util.ArrayList;
//import java.util.Arrays;
//import java.util.List;
//import java.util.PriorityQueue;
//import java.util.StringTokenizer;
//
///**
// * https://www.luogu.com.cn/problem/P8796
// * 这题维护的信息是，每个区间被修改了哪些字符。和原数组没有关系，在最后询问时遍历所有区间的修改信息去修改原数组。 好难想啊。。。。
// */
//public class H区间修改2 {
//	static int maxn = (int) (1e5 + 10);
//	static char[] src;
//	static int n, m;
//	static Tree[] tree;
//	static int tn;
//
//	public static void main(String[] args) {
//		Reader sc = new Reader();
//		src = sc.nextLine().toCharArray();
//		m = sc.nextInt();
//		n = src.length;
//		tn = (int) Math.pow(2, 1 + Math.ceil(Math.log(n) / Math.log(2)));
//		tree = new Tree[tn];
//		build(1, 1, n);
//		while (m-- > 0) {
//			int l = sc.nextInt();
//			int r = sc.nextInt();
//			char s = sc.nextChar();
//			char e = sc.nextChar();
//			update(1, l, r, s, e);
//		}
//		dfs();
//		sc.pr.println(new String(src));
//		sc.pr.flush();
//	}
//
//	public static void dfs() {
//		int[] q=new int[n+2];
//		int h=0,t=0;
//		q[t++]=1;
//		while(h!=t) {
//			int cur=q[h++];
//			h%=q.length;
//			if(tree[cur].tag) {
//				for(int i=tree[cur].l-1;i<tree[cur].r;i++) {
//					//树中src[i]对应的字符转化为c[src[i]-'a']
//					src[i]=tree[cur].c[src[i]-'a'];
//				}
//			}else {
//				int l=cur<<1;
//				int r=l|1;
//				if(l<tn&&tree[l]!=null) {
//					q[t++]=l;
//					t%=q.length;
//				}
//				if(r<tn&&tree[r]!=null) {
//					q[t++]=r;
//					t%=q.length;
//				}
//			}
//		}
//	}
//	
//	public static void build(int i, int l, int r) {
//		tree[i] = new Tree(l, r);
//		if (l == r) {
//			return;
//		}
//		int m = l + r >> 1;
//		build(i << 1, l, m);
//		build(i << 1 | 1, m + 1, r);
//	}
//
//	public static void update(int i, int l, int r, char s, char t) {
//		if (l <= tree[i].l && tree[i].r <= r) {
//			tree[i].lazy(s, t);
//		} else {
//			push(i);
//			int m = tree[i].l + tree[i].r >> 1;
//			if (l <= m) {
//				update(i << 1, l, r, s, t);
//			}
//			if (m < r) {
//				update(i << 1 | 1, l, r, s, t);
//			}
////			tree[i].c[s-'a']=s;
//		}
//	}
//
//	private static void push(int i) {
//		int l=i<<1;
//		int r=l|1;
//		if(tree[i].tag) {
//			for(int next=0;next<26;next++) {
//				if(tree[i].c[next]=='a'+next) continue;
//				tree[l].lazy(tree[l].c[next], tree[i].c[next]);
//				tree[r].lazy(tree[r].c[next], tree[i].c[next]);
//			}
//			tree[i].tag=false;
//		}
//	}
//
//	static class Tree {
//		int l, r;
//		char[] c = new char[26];
//		boolean tag;
//		
//
//		@Override
//		public String toString() {
//			return "Tree [l=" + l + ", r=" + r + ", c=" + Arrays.toString(c) + ", tag=" + tag + "]";
//		}
//
//		public Tree(int l, int r) {
//			this.l = l;
//			this.r = r;
//			// 当前区间的每个字符都没有被覆盖
//			for (int i = 0; i < 26; i++) {
//				c[i] = (char) (i + 'a');
//			}
//		}
//
//		// 把当前的s改为t
//		public void lazy(char s, char t) {
//			for(int i=0;i<26;i++) {
//				if(c[i]==s) {
//					c[i] = t;
//				}
//			}
//			tag = true;
//		}
//
//	}
//
//	static class Reader {
//		private PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
//		private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//		private StringTokenizer tokenizer = new StringTokenizer("");
//
//		private String innerNextLine() {
//			try {
//				return reader.readLine();
//			} catch (IOException ex) {
//				return null;
//			}
//		}
//
//		public boolean hasNext() {
//			while (!tokenizer.hasMoreTokens()) { // 内存中没有
//				String nextLine = innerNextLine();
//				if (nextLine == null) { // 且没有下一行
//					return false;
//				}
//				tokenizer = new StringTokenizer(nextLine); // 读入一行
//			}
//			return true;
//		}
//
//		public String nextLine() {
//			tokenizer = new StringTokenizer(""); // 清空内存中的字符
//			return innerNextLine();
//		}
//
//		public void clear() {
//			tokenizer = new StringTokenizer("");
//		}
//
//		public String next() {
//			hasNext();
//			return tokenizer.nextToken();
//		}
//
//		public int nextInt() {
//			return Integer.parseInt(next());
//		}
//
//		public char nextChar() {
//			return next().charAt(0);
//		}
//
//		public long nextLong() {
//			return Long.parseLong(next());
//		}
//
//		public double nextDouble() {
//			return Double.parseDouble(next());
//		}
//
//		// public BigInteger nextBigInt() {
////	        return new BigInteger(next());
////	    }
//
//	}
//
//}
